🟨最長回文字子序列(解法1)

題目

本題取自 Leetcode 516. Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence's length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".


Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".
 

Constraints:

1 <= s.length <= 1000
s consists only of lowercase English letters.

分析

本題要尋找給定字串當中最長的回文字子序列長度。

回文字指的是正著讀、倒著讀都一樣的文字(字數不限奇數偶數，因此abba、aba、aa、a都是回文字)

和day9遇到過的子字串定義不太相同，子序列可以由給定字串(或者陣列)當中取出任意的片段並重新串接，但順序要維持不變。例如'abcd'的子序列包含'abd'，但不包含'ca'(因為字母順序和原字串不同)。

那麼要如何找出題目所要求的「最長的回文字子序列」呢？

暴力破解(brute force)顯然是不現實的，因為每一個字母都可以取或者不取，光是暴力枚舉(enumerate)出所有的子序列就需要O(2^n)的指數時間，顯然必須尋找不同的途徑。

對於這種找最大/最小值，且暴力解明顯不通的時候，可以試著從「貪心一點」的角度來重構問題：

若一個字串是回文字，則最首字母和最尾字母必定相同。換言之：若一個字串的最首字母和最尾字母不同，則必定不為回文字。

因為「子序列」必須從原字串中切出，且字母順序必須維持不變，若一個字串的最首字母和最尾字母不同，則這個字串本身必定不符合「回文字子序列」的要求。既然如此，就必須至少捨棄掉字首或者字尾其中之一。

反過來說，若最首字母和最尾字母相同，則此字首/字尾必定包含於最長回文子序列當中。

分治法

舉例來說，給定一個字串'lilya'，先檢查頭尾是否相同，發現首尾不同，代表字首的'l'與字尾的'y'不可能同時存在於所求答案的「最長回文字子序列」當中。

因此，答案必定在「掐頭或者去尾」，也就是'ilya'和'lily'當中其中一個。

若首尾相同，則所求答案的「最長回文字子序列」必定包含這兩個字母，可以直接扣除這兩個字母繼續比對。

例如給定一個字串'tenet'，由於首尾字母相同，答案的「最長回文字子序列」必定包含't...t'，因此繼續比對中間的'ene'。

設計狀態、找出轉移式與最小問題

狀態：以lenLPS(i,j)代表給定字串s的子字串s[i:j+1]當中的最長回文子序列長度。

轉移式：

若i>j：空字串(邊界條件)，lenLPS(i,j) = 0

若i==j：剩一個字母(最小子問題)，lenLPS(i,j) = 1

若s[i] == s[j]：lenLPS(i,j) = 2 + lenLPS(i+1, j-1)

若s[i] != s[j]：lenLPS(i,j) = max( lenLPS(i+1, j), lenLPS(i,j-1) )

母問題：lenLPS(0,len(s)-1)

以字串字串'lilya'為例，遞迴求解的過程如下圖：

實作

Top-Down DP

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        @cache
        def lenLPS(i,j):
            if i>j: 
                return 0
            if i==j: 
                return 1
            if s[i]==s[j]: 
                return 2 + lenLPS(i+1,j-1)
            return max(lenLPS(i+1,j), lenLPS(i,j-1))
        return lenLPS(0, len(s)-1)

Bottom-Up DP

前述的遞迴邏輯，在設計Bottom-Up時計算順序該如何規劃呢？

參考'lilya'的例圖，發現要從圖中的由下往上計算(因為上面的子問題會用到下面的子問題答案)。而並不是由特定的index順序開始計算，而是在s的子字串中從短到長的順序計算。

因此，和前述Top-Down的狀態稍有不同

我們定義狀態l來代表所檢查子字串的長度，並且以狀態i來代表該子字串的起始位置。

並且用dp[l,i]記錄s[i:i+l]子字串本身所包含的最長回文子序列長度。

因此，最小問題：dp[0]全為0(因為代表空字串)，dp[1]全為1(因為長度為1的子字串必為回文字)。

之所以需要dp[0]，是因為當計算dp[2]時若是回文字，轉移式會需要用到dp[0]，為了避免index overflow，同時也不想要在轉移式中多加一個條件判斷，就和前幾天的矩陣題一樣，採用這個增加一列邊界值的做法。

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0]*n,[1]*n]
        for l in range(2, n+1):
            dp.append([
                2+dp[-2][i+1] if s[i]==s[i+l-1] else max(dp[-1][i:i+2]) 
                for i in range(0,n-l+1)])
        return dp[-1]

如果還是看不太懂，可以將上例的dp逐行印出，能看出就是前述'lilya'例圖中，子問題答案的反序：

[0, 0, 0, 0, 0]
[1, 1, 1, 1, 1]
[1, 1, 1, 1]
[3, 1, 1]
[3, 1]
[3]

本例一樣可以改寫為Rolling的形式來節省空間，由於轉移式會用到dp[-2]，代表需要保留最後兩列的狀態。

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        pre = [0]*n
        cur = [1]*n
        for l in range(2, n+1):
            pre, cur = cur, [
                2+pre[i+1] if s[i]==s[i+l-1] else max(cur[i:i+2]) 
                for i in range(0,n-l+1)]
        return cur[0]

複雜度分析

時間複雜度

時間複雜度 = 狀態轉移數 x 計算複雜度

本題的狀態數 = O(n^2)，n = len(s)

計算複雜度為O(1)

因此總時間複雜度 = O(n^2)

空間複雜度

空間複雜度 ＝ 狀態數 ＝ O(n^2)

若採用Rolling Bottom Up DP的技巧，則降低一個維度，空間複雜度 ＝ O(n)

🟨最長回文字子序列(解法2)

分析

除了前述的解題邏輯，若你對昨天的最長共同子序列(LCS)題型印象深刻，本題還可以重述如下：

求給定字串s以及其反序字串ss = s[::-1]的最長共同子序列(LCS)長度。

圖上的紅色線，表示s與ss之間的LCS的對應關係，而綠色線則代表原本題目所求，字串s本身的LPS。可以發現，兩者就是一樣的。

實作

可以直接拿昨天的LCS來用，只需要把text1和text2分別代入s與s[::-1]即可

因為原本就是同一個字串，只是反序，所以不存在「兩個字串不共用」的字母，因此和昨天的題目不同，這部分的優化可以不做(做了也沒有效果)。

結語

LPS也是我很喜歡的題型。兩種思維、兩個不同的狀態設計與轉移式，竟然能夠殊途同歸並且有相同的時間、空間複雜度。特別是第二種解法，利用了回文字本身的特殊性質，相當有巧思。

以上為Day12的內容！感謝你的閱讀，如果有不同的想法或心得，歡迎留言一同討論！

本文也同步登載在我的個人部落格，記錄我的學習筆記與生活點滴，歡迎來逛逛。

明天會繼續看字串題型的例題。